package astar.model;

import java.awt.Point;
import java.util.ArrayList;

import astar.model.Calc;

/**
*
* @author Artur Ataide, Andre Ventura
* @date Junho 2014
*
*/
public class AStar{

	private static final Point START_POINT = new Point(192, 48);
	private static final Point END_POINT = new Point(260, 508);
	private ArrayList<Point> closedList;
	private ArrayList<Point> openList;
	private double[][] pixels;

	/**
	*
	* Construtor da classe AStar. Recebe um array bi-dimensional de doubles
	* estando nele contido os valores da cor de cada pixel. Cria uma lista
	* fechada e uma lista aberta essenciais para realizar o algoritmo.
	*
	* @param pixels Array bi-dimensional contendo a intensidade da cor de cada
	* pixel, normalizada de 0 a 1, sendo 0 mais claro e 1 mais escuro. 
	*
	*/
	public AStar(double[][] pixels){
		final int N = 250;
		Calc calc = new Calc();
		calc.setTotalTime(0);
		this.pixels = pixels;
		for (int i = 0; i < N ; i++) {
			this.closedList = new ArrayList<Point>();
			this.openList = new ArrayList<Point>();
			
			this.doAStar(calc);	
			if(i == 1)
 				calc.saveToTxt("points", calc.getPointTime());
 			calc.setAlgTime(); 
			calc.setTotalTime(calc.getTotalTime().get(i) + calc.getAlgTime().get(i));					
 						
		}		
		calc.saveToTxt("astar_avg", calc.getAlgTime());
		calc.saveToTxt("astar", calc.getTotalTime());
		System.out.println();
	}

	/**
	*
	* Método onde é encontrado o caminho (path) com menos custo entre os dois 
	* pontos, utilizando o algoritmo A* (A Star). 
	* http://en.wikipedia.org/wiki/A*_search_algorithm
	*
	* @param calc Objeto da classe Calc que permite efetuar os cálculos dos 
	* tempos de execução.
	*
	*/
	private void doAStar(Calc calc){		
		ArrayList<Double> addPoints = new ArrayList<Double>();
		int iPoints = 1;
		addPoints.add(0.0);
 		Point current = this.START_POINT;
 		this.closedList.add(current);
 		
 		while (!AStar.END_POINT.equals(current)) {
 			// tempo inicial da pesquisa do ponto
			double time = System.nanoTime() / 1000000000.0;

 			// encontrar todos os vizinhos do ponto a ser analizado.
 			ArrayList<Point> neighbour = this.neighbour(current); 
 			// Array lista onde os valores da cor serão gravados.
 			ArrayList<Double> values = new ArrayList<Double>();
 			// obter os valores da cor dos vizinhos do ponto a ser analizado
 			// e colocar o ArrayList 'values'.
 			for (Point p : neighbour) {
 				values.add(f(p));
 			}
 			// ver qual o valor minimo da cor e gravar o index desse valor.
 			int index = 0;
 			double value = Double.MAX_VALUE;
 			
 			for (int i = 0; i < values.size(); i++) {
 				if (values.get(i) < value) {
 					value = values.get(i);
 					index = i;
 				}
 			}
 			// através do index obtido, obtem-se o index do vizinho com mais
 			// intensidade de cor (menor custo).
 			current = neighbour.get(index);
 			this.closedList.add(current);

 			//tempo final da pesquisa do ponto
 			time = (System.nanoTime() / 1000000000.0) - time;
 			addPoints.add(addPoints.get(iPoints - 1) + time);
 			iPoints++;
 			calc.setPointTime(time); 			
 		}	 	
 		calc.saveToTxt("sum_points", addPoints);	
 	}


 	/**
 	*
 	* Método que devolve um ArrayList com todos os vizinhos do ponto recebido,
 	* sendo que os mesmos não poderão estar na lista fechada.
 	*
 	* @param current Ponto atual que irá ser utilizado para a obtenção de 
 	* vizinhos.
 	*
 	* @return ArrayList contendo os vizinhos do ponto atual.
 	*
 	*/
	private ArrayList<Point> neighbour(Point current){
 		ArrayList<Point> neighbourPoints = new ArrayList<Point>();
 		for (int x = -1; x < 2; x++) {
			for (int y = -1; y < 2; y++) {
		 		if (x != 0 && y != 0) {
		 			Point p = new Point(current.x + x, current.y + y);
		 			if (!this.closedList.contains(p)) {
		 				neighbourPoints.add(p);
		 			}
		 		}
		 	}
		 }
		 return neighbourPoints;
	 }

	 /**
	*
	* Cálculo da função f (f = g + h). A heuristica é dividida pelo valor da 
	* variável 'STEP' para que os passos a ser dados sejam menores, logo o 
	* caminho é calculado com melhor exatidão.
	* 
	* @param open Ponto a ser calculado. Irá obter-se o valor f desse ponto.
	*
	* @return O valor da função f (f = g + h).
	*
	*/
	private double f(Point open){
		final int STEP = 20;
		return (this.h(open) / STEP)  + this.g(open);//
	}

	/**
	*
	* Calculo do g da função (f = g + h). É devolvida o valor da intensidade
	* da cor normalizada, entre zero e um, sendo que zero é mais brilhante.
	*
	* @param p Ponto ao qual irá ser conhecida o valor da intensidade da cor.
	*
	* @return O valor do g da função (f = g + h).
	*
	*/
	private double g(Point p){
		final int MAX_VALUE = 255;
		return 1 - (this.pixels[p.x][p.y] / MAX_VALUE);
	}

	/**
	*
	* Método que devolve o h da função (f = g + h). Representa a heuristica
	* utilizada no calculo deste algoritmo.
	* fonte: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
	*
	* @param p Ponto que irá ser utilizado para obter o valor da heuristica.
	*
	* @return O valor do h da função (f = g + h).
	*
	*/
	private double h(Point p){
		int dx = p.x - AStar.END_POINT.x;
		int dy = p.y - AStar.END_POINT.y;
		return Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
	}

	
	/**
	*
	* Método que devolve a lista fechada, que contém os pontos com o caminho
	* com menos custo do ponto de origem ao ponto de destino. Este método 
	* devolve o ArrayList de pontos que irá ser necessário para o desenho do 
	* caminho.
	*
	* @return O ArrayLista contendo os pontos da lista fechada. Pontos esses
	* que representam o caminho obtido através o algoritmo A*.
	*
	*/
	public ArrayList<Point> getClosedList(){
		return this.closedList;
	}

}